package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 60. 排列序列
 * @date 2025/5/12 10:53
 */
public class E60 {
    private int count = 0;
    private boolean stop = false;

    /**
     * 能解决大多数情况，思路是跳过前面的组合，直接确定第一位数字，重新计算k，然后回溯求出第k个组合
     *
     * @param n n
     * @param k k
     * @return s
     */
    public String getPermutation1(int n, int k) {
        int f = factorial(n - 1);
        int y = k % f;
        int first = k / f + 1;
        StringBuilder builder = new StringBuilder();
        builder.append(first);
        StringBuilder curr = new StringBuilder();
        dfs(n, first, y, builder, new boolean[n + 1], curr);
        return builder.toString();
    }

    public int factorial(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        return n * factorial(n - 1);
    }

    private void dfs(int n, int first, int y, StringBuilder builder, boolean[] visited, StringBuilder curr) {
        if (curr.length() == n - 1) {
            count++;
            if (count == y) {
                builder.append(curr);
                stop = true;
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (i == first) continue;
            if (visited[i]) continue;
            curr.append(i);
            visited[i] = true;
            dfs(n, first, y, builder, visited, curr);
            if (stop) return;
            visited[i] = false;
            curr.setLength(curr.length() - 1);
        }
    }

    /**
     * 巧妙
     * @param n n
     * @param k k
     * @return s
     */
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        StringBuilder result = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        k--;
        while (n > 0) {
            n--;
            int f = factorial[n];
            int index = k / f;
            k = k % f;
            result.append(nums.remove(index));
        }
        return result.toString();
    }
}
